package leetcode.D100.T76;

import java.util.HashMap;
import java.util.Map;

class Solution {
    /*// 一刷
    public String minWindow(String s, String t) {
        int left = 0, right = 0;
        int valid = 0, len = Integer.MAX_VALUE, start = 0;
        Map<Character, Integer> need = new HashMap<>(), window = new HashMap<>();
        for(int i=0; i<t.length(); ++i) {
            int origin = need.getOrDefault(t.charAt(i), 0);
            need.put(t.charAt(i), origin+1);
            window.putIfAbsent(t.charAt(i), 0);
        }
        while(right < s.length()) {
            char c = s.charAt(right);
            right++;
            if(need.containsKey(c)) {
                int origin = window.get(c);
                window.put(c, origin+1);
                if(origin + 1 == need.get(c)) {
                    valid++;
                }
            }
            while(valid == need.size()) {
                if(right - left < len) {
                    len = right - left;
                    start = left;
                }
                char d = s.charAt(left++);
                if(need.containsKey(d)) {
                    int origin = window.get(d);
                    window.put(d, origin-1);
                    if(origin == need.get(d)) {
                        valid--;
                    }
                }
            }
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start+len);
    }*/
    // 二刷
//    public String minWindow(String s, String t) {
//        int start = 0;
//        int left = 0, right = 0;
//        int valid = 0, minLen = Integer.MAX_VALUE;
//        Map<Character, Integer> need = new HashMap<>();
//        Map<Character, Integer> window = new HashMap<>();
//        for(int i=0; i<t.length(); ++i) {
//            int origin = need.getOrDefault(t.charAt(i), 0);
//            need.put(t.charAt(i), origin+1);
//            window.put(t.charAt(i), 0);
//        }
//        while(right < s.length()) {
//            char c = s.charAt(right++);
//            if(need.containsKey(c)) {
//                int origin = window.get(c);
//                window.put(c, origin+1);
//                if(origin + 1 == need.get(c)) {
//                    valid++;
//                }
//            }
//            while(valid == need.size()) {
//                if(right - left < minLen) {
//                    start = left;
//                    minLen = right - left;
//                }
//                char d = s.charAt(left++);
//                if(need.containsKey(d)) {
//                    int origin = window.get(d);
//                    if(origin == need.get(d)) {
//                        valid--;
//                    }
//                    window.put(d, origin-1);
//                }
//            }
//        }
//        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
//    }

    // 三刷
    /*public String minWindow(String s, String t) {
        int valid = 0, minLen = s.length()+1, start = 0;
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
        int left = 0, right = 0;
        for(int i=0; i<t.length(); ++i) {
            int origin = need.getOrDefault(t.charAt(i), 0);
            need.put(t.charAt(i), origin+1);
            window.put(t.charAt(i), 0);
        }
        while(right < s.length()) {
            char c = s.charAt(right++);
            if(need.containsKey(c)) {
                int origin = window.get(c);
                window.put(c, origin+1);
                if(origin + 1 == need.get(c)) {
                    valid++;
                }
            }
            while(valid == need.size()) {
                int len = right - left;
                if(len < minLen) {
                    minLen = len;
                    start = left;
                }
                char d = s.charAt(left++);
                if(need.containsKey(d)) {
                    int origin = window.get(d);
                    window.put(d, origin-1);
                    if(origin == need.get(d)) {
                        valid--;
                    }
                }
            }
        }
        return minLen <= s.length() ? s.substring(start, start+minLen) : "";
    }*/

    // 四刷
    /*public String minWindow(String s, String t) {
        int minLen = Integer.MAX_VALUE, start = 0, left = 0, right = 0, valid = 0;
        Map<Character, Integer> window = new HashMap<>(), need = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            need.put(t.charAt(i), need.getOrDefault(t.charAt(i), 0)+1);
        }
        while(right < s.length()) {
            // 扩展
            char c = s.charAt(right++);
            if (need.containsKey(c)) {
                int origin = window.getOrDefault(c, 0);
                if ((origin+1) == need.get(c)) {
                    valid++;
                }
                window.put(c, origin+1);
            }
            while(valid == need.size()) {
                if ((right-left) <= minLen) {
                    minLen = right - left;
                    start = left;
                }
                char d = s.charAt(left++);
                if(window.containsKey(d)) {
                    int originVal = window.get(d);
                    if (originVal == need.get(d)) {
                        valid--;
                    }
                    window.put(d, originVal-1);
                }
            }
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start+minLen);
    }*/

    // 五刷
    /*public String minWindow(String s, String t) {
        int left = 0, right = 0, valid = 0, start = 0, minLen = Integer.MAX_VALUE;
        Map<Character, Integer> window = new HashMap<>();
        Map<Character, Integer> need = new HashMap<>();
        for (int i=0; i<t.length(); ++i) {
            int origin = need.getOrDefault(t.charAt(i), 0);
            need.put(t.charAt(i), origin+1);
        }
        while (right < s.length()) {
            char c = s.charAt(right++);
            if (need.containsKey(c)) {
                int origin = window.getOrDefault(c, 0);
                if (origin + 1 == need.get(c)) {
                    valid++;
                }
                window.put(c, origin+1);
            }
            while (valid == need.size()) {
                int len = right - left;
                if (len < minLen) {
                    minLen = len;
                    start = left;
                }
                char d = s.charAt(left++);
                if (need.containsKey(d)) {
                    int origin = window.get(d);
                    if (origin == need.get(d))
                        valid--;
                    window.put(d, origin-1);
                }
            }
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start+minLen);
    }*/

    // 六刷
    public String minWindow(String s, String t) {
       int left = 0, right = 0, start = 0, minLen = Integer.MAX_VALUE, valid = 0;
       Map<Character, Integer> window = new HashMap<>(), need = new HashMap<>();
       for (int i=0; i<t.length(); ++i) {
           char c = t.charAt(i);
           need.put(c, need.getOrDefault(c, 0) + 1);
       }
       while (right < s.length()) {
           char c = s.charAt(right++);
           if (need.containsKey(c)) {
               int origin = window.getOrDefault(c, 0);
               if (origin + 1 == need.get(c))
                   valid++;
               window.put(c, origin + 1);
           }
           while (valid == need.size()) {
               if (right - left < minLen) {
                   minLen = right - left;
                   start = left;
               }
               char d = s.charAt(left++);
               if (need.containsKey(d)) {
                   int origin = window.get(d);
                   if (origin == need.get(d)) {
                       valid--;
                   }
                   window.put(d, origin - 1);
               }
           }
       }
       return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }
}